// https://leetcode.cn/problems/evaluate-boolean-binary-tree/description/

// 算法思路总结：
// 1. 递归计算布尔表达式二叉树的值
// 2. 叶子节点：0表示false，1表示true
// 3. 非叶子节点：2表示OR运算，3表示AND运算
// 4. 递归计算左右子树结果，根据操作符进行逻辑运算
// 5. 时间复杂度：O(n)，空间复杂度：O(h)（递归栈深度）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    bool evaluateTree(TreeNode* root) 
    {
        if (root->left == nullptr) 
            return root->val;

        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);

        if (root->val == 2)
            return left | right;
        else 
            return left & right;

        return true;
    }
};

int main()
{
    vector<string> tree1 = {"2", "1", "3", "null", "null", "0", "1"};
    vector<string> tree2 = {"0"};

    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    cout << sol.evaluateTree(root1) << endl;
    cout << sol.evaluateTree(root2) << endl;

    return 0;
}